package com.huangkailong.leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * <h1>无重复字符的最长子串</h1>
 *
 * 给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。<br/>
 *
 * 示例1:<br/>
 *
 * 输入: s = "abcabcbb"<br/>
 * 输出: 3 <br/>
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。<br/>
 *
 * 示例 2:<br/>
 * 输入: s = "bbbbb"<br/>
 * 输出: 1<br/>
 * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。<br/>
 *
 * 示例 3:<br/>
 * 输入: s = "pwwkew"<br/>
 * 输出: 3<br/>
 * 解释: 因为无重复字符的最长子串是"wke"，所以其长度为 3。<br/>
 *     请注意，你的答案必须是 子串 的长度，"pwke"是一个子序列，不是子串。<br/>
 *
 * 示例 4:<br/>
 * 输入: s = ""<br/>
 * 输出: 0<br/>
 *
 * 提示：<br/>
 *
 * 0 <= s.length <= 5 * 104<br/>
 * s由英文字母、数字、符号和空格组成<br/>
 *
 * @author huangkl
 * @since 1.0.0
 */
public class LengthOfLongestSubstring {

    /**
     * 暴力枚举
     */
    public static int solution1(String s) {
        if(s == null || s.length() == 0){
            return 0;
        }

        Set<Character> distinct = new HashSet<>();
        int maxLength = 0;
        for (int i = 0; i < s.length(); i++) {
            distinct.add(s.charAt(i));
            for (int j = i+1; j < s.length(); j++) {
                char charAt = s.charAt(j);
                if(distinct.contains(charAt)){
                    break;
                }
                distinct.add(charAt);
            }
            maxLength = Math.max(maxLength, distinct.size());
            distinct.clear();
        }
        return maxLength;
    }

    /**
     * 滑动窗口
     */
    public static int solution2(String s) {
        int len = s.length();
        if(s == null || len == 0){
            return 0;
        }

        Set<Character> distinct = new HashSet<>();
        int maxLength = 0;
        int j = -1;
        for (int i = 0; i < len; i++) {
            if(i != 0){
                distinct.remove(s.charAt(i-1));
            }
            while (j+1 < len && !distinct.contains(s.charAt(j+1))){
                distinct.add(s.charAt(j+1));
                j++;
            }
            maxLength = Math.max(maxLength, distinct.size());
            if(j+1 >= len){
                break;
            }
        }
        return maxLength;
    }
}
